<!doctype html>
<html lang="en">

	<head>
		<meta charset="utf-8">

		<title>Experimental Boost.MSM-lite</title>

		<meta name="description" content="A framework for easily creating beautiful presentations using HTML">
		<meta name="author" content="Hakim El Hattab">

		<meta name="apple-mobile-web-app-capable" content="yes">
		<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">

		<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, minimal-ui">

		<link rel="stylesheet" href="css/reveal.css">
    <link rel="stylesheet" href="css/theme/league.css" id="theme">

		<!-- Code syntax highlighting -->
		<link rel="stylesheet" href="lib/css/zenburn.css">

		<!-- Printing and PDF exports -->
		<script>
			var link = document.createElement( 'link' );
			link.rel = 'stylesheet';
			link.type = 'text/css';
			link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.css';
			document.getElementsByTagName( 'head' )[0].appendChild( link );
		</script>
	</head>

	<body>

		<div class="reveal">
			<div class="slides">
          <section data-markdown=""
                   data-separator="^====+$"
                   data-separator-vertical="^----+$"
                   data-notes="^Note:">
					<script type="text/template">
C++Now 2016-2017

# C++14 Meta State Machine Library

Kris Jusiak

==============================================================================

##UML State Machine

----

**UML State Machine** (SM) depict the dynamic behavior of an entity based on its response to events, 
showing how the entity reacts to various events depending on the current state that it is in

> Formerly called **UML state chart** in UML 1

----

####State Machine Concepts

![State Machine](images/sm.png)

----

| UML Concept         | Description |
| ------------------- | ----------- |
| Event               | Trigger which affects the system, ex. `button click`           |
| State               | Captures aspect of relavant system history, ex. `Playing`            |
| Transition          | Conditionally update current state, ex. `src_state + event [ guard ] / action -> dst_state`           |
| Orthogonal Region   | Sudo parallel state machines, ex. `Play and Quit` |

----

##Do I need a State Machine?

----

###No, But...

----

* SM promotes better design
  * Compliant with UML documentation

* SM creates easier to maintain code
  * Declarative approach / Expresses `WHAT`, not `HOW`!

* SM creates easy to test code
  * Can be tested in isolation without trying to reach all conditional branches

----

###Example

----

####Swap Items
![Swap Items](images/sm_swap_items.png)

----

###No State Machine

```cpp
void handle(auto event) {
  if (event == click && !isAnimating) {
    select_item();
    ++itemsSelected;

    if (itemsSelected == 2) {
      swap_items();
      animate();
      isAnimating = true;
    }
  } else if(event == done) {
    isAnimating = false;
    itemsSelected = 0;
  }
}
```

----

###State Machine (Pseudo-code)

```cpp
transition_table {
  *Wait_For_First_Item + click / select_item -> Wait_For_Second_Item,
   Wait_For_Second_Item + click / select_item, swap_items -> Animate,
   Animate + on_entry / play_animation(),
   Animate + done -> Wait_For_First_Item
};
```

==============================================================================

##MSM-lite vs Boost.MSM-eUML vs Boost.Statechart

----

##Overview

----

| Library     | MSM-lite    | Boost.MSM-eUML  | Boost.Statechart |
| --------    | ----------- | --------------- | ---------------- |
| Standard    | C++14       | C++98/03        | C++98/03         |
| Version     | 1.0.1       | 1.61            | 1.61             |
| License     | Boost 1.0   | Boost 1.0       | Boost 1.0        |
| Linkage     | header only | header only     | header only      |

----

##Implementation details

----

| Library            | MSM-lite    | Boost.MSM-eUML  | Boost.Statechart |
| ------------------ | ----------- | --------------- | ---------------- |
| UML                | 2.0         | 2.0             | 1.5              |
| RTTI               | -           | -               | ✓                |
| Exceptions         | -           | -               | ✓                |
| Memory Allocations | -           | -               | ✓                |

----


##Features

----

##UML features

----

| Library              | MSM-lite | Boost.MSM-eUML | Boost.Statechart |
| -------------------- | -------- | -------------- | ---------------- |
| Transition           | ✓        | ✓              | ✓                |
| Anonymous transition | ✓        | ✓              | ✓                |
| Internal transition  | ✓        | ✓              | ✓                |
| Local transitions    | -        | -              | -                |

----

| Library              | MSM-lite | Boost.MSM-eUML | Boost.Statechart |
| -------------------- | -------- | -------------- | ---------------- |
| State entry/exit     | ✓        | ✓              | ✓                |
| Guard                | ✓        | ✓              | ✓                |
| Action               | ✓        | ✓              | ✓                |
| Event defering       | ~        | ✓              | ✓                |
| Error handling       | ✓        | ✓              | ✓                |

----

| Library              | MSM-lite | Boost.MSM-eUML | Boost.Statechart |
| -------------------- | -------- | -------------- | ---------------- |
| Initial state        | ✓        | ✓              | ✓                |
| Terminate State      | ✓        | ✓              | ✓                |
| Explicit entry       | ✓        | ✓              | ✓                |
| Explicit exit        | -        | ✓              | ✓                |
| Fork                 | -        | ✓              | -                |

----

| Library              | MSM-lite | Boost.MSM-eUML | Boost.Statechart |
| -------------------- | -------- | -------------- | ---------------- |
| Orthogonal regions   | ✓        | ✓              | ✓                |
| Sub / Composite      | ✓        | ✓              | ✓                |
| Shallow History      | ✓        | ✓              | ✓                |
| Deep History         | ~        | ~              | ✓                |


----

##Non-UML features

----

| Library              | MSM-lite | Boost.MSM-eUML | Boost.Statechart |
| -------------------- | -------- | -------------- | ---------------- |
| Any event            | -        | ✓              | -                |
| Flags                | -        | ✓              | -                |
| Interrupt state      | -        | ✓              | -                |
| State Visitor        | ✓        | ✓              | ✓                |
| Serialization        | -        | ✓              | -                |
| Dispatcher           | ✓        | -              | -                |
| Asynchronous SM      | -        | -              | ✓                |

----

##Example

----

####Simple State Machine

<img width="40%" src="images/sm_example.png" />

----

##Boost.MSM-eUML

----

###Events

```cpp
BOOST_MSM_EUML_EVENT(play)
```
-----

###States

```cpp
BOOST_MSM_EUML_STATE((), Idle)
BOOST_MSM_EUML_STATE((), Playing)
```

----

###Actions

```cpp
BOOST_MSM_EUML_ACTION(start) {
template <class FSM, class EVT, class SourceState, class TargetState>
  void operator()(EVT const &, FSM &, SourceState &, TargetState &) {
    // ...
  }
};
```

----

###Transition table

```cpp
BOOST_MSM_EUML_TRANSITION_TABLE((
  Playing == Idle + play / start
), transition_table)
```

----

###State Machine

```cpp
BOOST_MSM_EUML_ACTION(Log_No_Transition){
  template <class FSM, class Event>
  void operator()(Event const &, FSM &, int state) {
      // ...
  }
};
```

```cpp
BOOST_MSM_EUML_DECLARE_STATE_MACHINE((
  transition_table,
  init_ << Idle,
  no_action, // entry
  no_action, // exit
  attributes_ << no_attributes_,
  configure_ << no_exception << no_msg_queue,
  Log_No_Transition
), player_);

using player = msm::back::state_machine<player_>;
```

----

###Process event

```cpp
player sm;
sm.process_event(play);
```

----

###Boost.Statechart

----

###Events

```cpp
struct play : sc::event<play> { };
```

----

###Actions

```cpp
struct player : sc::state_machine<player, Idle> {
  void start(play const &) {
    // ...
  }
}
```

----

###States

```cpp
struct Idle : sc::simple_state<Idle, player> {
  using reactions = mpl::list<
    sc::transition<play, Playing, player, &player::start>
  >;
};

struct Playing : sc::simple_state<Playing, player> {
  using reactions = mpl::list<>;
};
```

----

###Process event

```cpp
player sm;
sm.process_event(play());
```

----

###Experimental Boost.MSM-lite

----

###Events

```cpp
struct play { };
```

----

###State Machine

```cpp
struct player {
  auto configure() {
    return make_transition_table(
      "Idle"_s + event<play> / []{ ... } = "Playing"_s
    )
  )
);
```
----

###Process event

```cpp
msm::lite::sm<player> sm;
sm.process_event(play{});
```

----


##Benchmarks

----

###Environment

----

###2.3 GHz Intel Core i7 / 16 GB 1600 Mhz DDR3

---

`CXXFLAGS: -O2 -s`

----

###[Simple Test](https://github.com/boost-ext/msm-lite/tree/master/test/pt/simple)

| Events | States | Transitions | Process Events |
| ------ | ------ | ----------- | -------------- |
| 6 | 5 | 12 | 1'000'000 |

----

| Clang-3.7        |       MSM-lite | Boost.MSM-eUML   | Boost.Statechart  |
|------------------|----------------|------------------|-------------------|
| Compilation time | 0.144s         | 3.855s           | 1.028s            |
| Execution time   | 15ms           | 17ms             | 1232ms            |
| Memory usage     | 14b            | 32b              | 200b              |
| Executable size  | 11K            | 91K              | 59K               |

----

| GCC-5.2          |       MSM-lite | Boost.MSM-eUML   | Boost.Statechart  |
|------------------|----------------|------------------|-------------------|
| Compilation time | 0.175s         | 7.879s           | 1.790s            |
| Execution time   | 15ms           | 19ms             | 929ms             |
| Memory usage     | 14b            | 32b              | 224b              |
| Executable size  | 11K            | 67K              | 63K               |

----

###[Composite Test](https://github.com/boost-ext/msm-lite/tree/master/test/pt/composite)

| Events | States | Transitions | Process Events |
| ------ | ------ | ----------- | -------------- |
| 8 | 5 + 3 | 12 + 4 | 1'000 * 1'000 |

----

| Clang-3.7        |       MSM-lite | Boost.MSM-eUML   | Boost.Statechart   |
|------------------|----------------|------------------|--------------------|
| Compilation time | 0.184s         | 4.526s           | 1.293s             |
| Execution time   | 10ms           | 14ms             | 491ms              |
| Memory usage     | 20b            | 60b              | 200b               |
| Executable size  | 15K            | 111K             | 83K                |

----

| GCC-5.2          |       MSM-lite | Boost.MSM-eUML   | Boost.Statechart   |
|------------------|----------------|------------------|--------------------|
| Compilation time | 0.248s         | 9.363s           | 2.037s             |
| Execution time   | 9ms            | 13ms             | 404ms              |
| Memory usage     | 20b            | 60b              | 224b               |
| Executable size  | 12K            | 91K              | 83K                |

----

##[Complex Test](https://github.com/boost-ext/msm-lite/tree/master/test/pt/complex)

| Events | States | Transitions | Process Events |
| ------ | ------ | ----------- | -------------- |
| 50 | 50 | 50 | 1'000'000 |

----

| Clang-3.7        |       MSM-lite | Boost.MSM-eUML   | Boost.Statechart   |
|------------------|----------------|------------------|--------------------|
| Compilation time | 0.582s         | 1m15.935s        | 3.661s             |
| Execution time   | 69ms           | 81ms             | 6221ms             |
| Memory usage     | 102b           | 120b             | 200b               |
| Executable size  | 35K            | 611K             | 343K               |

----

| GCC-5.2          |       MSM-lite | Boost.MSM-eUML   | Boost.Statechart   |
|------------------|----------------|------------------|--------------------|
| Compilation time | 0.816s         | 52.238s          | 4.997s             |
| Execution time   | 72ms           | 77ms             | 5520ms             |
| Memory usage     | 102b           | 120b             | 224b               |
| Executable size  | 35K            | 271K             | 215K               |

----

##More benchmarks

---

https://github.com/boost-ext/msm-lite/benchmarks

==============================================================================

##Experimental Boost.MSM-lite

==============================================================================

##Motivation

----

##[Boost.MSM-eUML](http://www.boost.org/doc/libs/1_60_0/libs/msm/doc/HTML/ch03s04.html) is awesome, but...

----

##Problems with Boost.MSM-eUML

----

###Long compilation times

----

###Huge binaries

----

###Long error messages

----

###Based on macros

----

###Functional programming emulation (C++03)

==============================================================================

##Overview

----

##A bit of history

----

2013

---

Version based on Boost.MSM-eUML

---

https://github.com/krzysztof-jusiak/msm

----

* Compiled slowly
* Long error messages
* Based on macros (inherited from Boost.MSM-eUML)

----

2016-2017

---

Version C++14 - v1.0.1

---

https://github.com/boost-ext/msm-lite

----

* One header (boost/msm-lite.hpp)
* 1.5k lines
* Neither Boost nor STL is required
* No 'virtual' methods
* No 'exceptions' (-fno-exceptions)

----

##Tested compilers

----

* [Clang-3.4+](https://travis-ci.org/boost-ext/msm-lite)

* [GCC-5.2+](https://travis-ci.org/boost-ext/msm-lite)

==============================================================================

##Design

----

##Goals

----

###Keep the Boost.MSM-eUML 'goodies'

----

###Design (front/back-end)

----

###Max performance

----

###Low memory usage

----

###eUML DSL

```cpp
src_state + event [ guard ] / action -> dst_state
```

----

###UML standard compliant (As much as possible)

----

##Eliminate Boost.MSM-eUML problems

----

###Speed up compilation times

* ####Up to 60x faster

----

###Reduce binary size

* ####3x smaller

----

###Better error messages

* ####Concepts emulation / no `MPL`

----

###Less boilerplate

* ####No macros

----

###Take advantage of modern C++ functional capabilities

* ####Lambdas as guards and actions

----

##Architecture

----

###Compile-time + run-time

---

> Generate jump table at compile-time
> and operates on it at run-time

----

##Front-end

----

###Responsible for providing an unified list of transitions

----

###DSL

> Domain Specific language

----

```cpp
"src_state"_s + event [ guard ] / action = "dst_state"_s
```

----

##Back-end

----

###Responsible for operating on transitions


==============================================================================

##User Guide

----

##Events

----

###Event declaration

```cpp
class my_event { ... };
```

----

###Event declaration on the fly

```cpp
using namespace msm;
auto event  = "event"_t;
```

> It's not standard!

-----

##States

-----

###State declaration

```cpp
auto idle = msm::state<class idle>{ };
```

-----

###State declaration on the fly

```cpp
using namespace msm;
auto state  = "idle"_s;
```

> It's not standard!

----

###State types

| State | Description | Notation | 
| ----- | ----------- | -------- |
| Initial state | Tells SM where to start | `*"state"_s` |
| Sub-SM | State which is a SM itself | `sm<...>` |
| History state | Remember Sub-SM state when reentered | `"state"_s(H)` |
| Terminate state | Indicates SM termination | `X` |

----

##Guards

----

###Guard is functor and MUST return boolean value

```cpp
auto guard_always_success = [] {
  return true;
};
```

```cpp
auto guard_with_dependencies = [](int, double) {
  return true;
};
```

```cpp
auto guard_with_dependencies_and_event = [](int, auto event, double) {
  return true;
};
```

----

##Actions

----

###Action is a functor and MUST not return

```cpp
auto action_empty = [] { };
```

```cpp
auto action_with_dependencies = [](int, double) { };
```

```cpp
auto action_with_dependencies_and_events = [](int, auto event, double) { };
```

----

##Transition table

----

###Transition Table DSL (Domain Specific language)

----

| Expression | Description |
|------------|-------------|
| state + event<e> [ guard ] | internal transition on event e when guard |
| src\_state / [] {} = dst\_state | anonymous transition with action |
| src\_state + event<e> = dst\_state | transition on event e without guard or action |

----

| Expression | Description |
|------------|-------------|
| src\_state + event<e> [ guard ] / action = dst\_state | transition from src\_state to dst\_state on event e with guard and action |
| src\_state + event<e> [ guard && (![]{return true;} && guard2) ] / (action, action2, []{}) = dst\_state | transition from src\_state to dst\_state on event e with guard and action |

----

###Make transition table

```cpp
using namespace msm;

make_transition_table(
  "src_state"_s + event<my_event> [guard] / action = "dst_state"_s
, "dst_state"_s + event<game_over> = X // 'X' - terminate state
);
```

----

###Orthogonal Regions

----

####Define Orthogonal regions by marking multiple states as initial
```cpp
using namespace msm;

make_transition_table(
 *"region_1"_s   + event<my_event1> [guard]/action = "dst_state1"_s
, "dst_state1"_s + event<game_over> = X,
//---------------------------------------------------------------//
 *"region_2"_s   + event<my_event2> [guard]/action = "dst_state2"_s
, "dst_state2"_s + event<game_over> = X
);
```

----

###State Machine

----

####Define State Machine

```cpp
class example {
public:
  auto configure() noexcept {
    using namespace msm;

    return make_transition_table(
     *"src"_s + event<my_event> [ guard ] / action = "dst"_s,
      "dst"_s + event<game_over> = X
    );
  }
};
```

####Declare State Machine

```cpp
msm::sm<example> sm;
```

----

##State Machine dependencies

> Required for guards and actions

----

####SM dependencies

```cpp
                            /-- event (injected from process_event)
                            |
auto guard = [](double d, auto event) { return true; }
                   |
                   \-------\
                           |
auto action = [](int i){}  |
                  |         |
                  |         |
                  \-\   /---/
                    |   |
msm::sm<example> s{42, 87.0};

// order in which parameters have to passed is not specificied
msm::sm<example> s{87.0, 42};
```

----

###Alternatively you can use Experimental Boost.DI

---

https://raw.githubusercontent.com/boost-ext/di

----


####Create SM using DI framework
```cpp
auto injector = di::make_injector<example>();
```

----

###Process Events

-----

####Process event by State Machine

```cpp
sm.process_event(my_event{});
```

----

##Dispatch events

> Useful for run-time events

----

####Dispatch SDL2 events

```cpp
struct game_over {
  static constexpr auto id = SDL_QUIT;
  // explicit game_over(const SDL_Event&) noexcept;
};

auto dispatch_event =
  msm::make_dispatch_table<SDL_Event
                         , SDL_FIRSTEVENT
                         , SDL_LASTEVENT>(sm);

SDL_Event event{SDL_QUIT};

// will call sm.process(game_over{});
dispatch_event(event, event.type);
```

----

##Handle errors

----

###Unexpected Event

----

####Handle unexpected event
```cpp
make_transition_table(
 *"src"_s + event<my_event> [ guard ] / action = "dst"_s
, "src"_s + unexpected_event<some_event> = X
);
```

```cpp
sm.process_event(some_event{}); // SM will enter terminate (X) state
```

----

##Exceptions

> Only if NOT compiled with `-fno-exceptions`

----

####Exception handling
```cpp
make_transition_table(
 *"state"_s + event<event> / []{throw std::runtime_error{"error"};}
,*"state"_s + exception<std::runtime_error> = X
, "state"_s + exception<std::logic_error> = X
, "state"_s + exception<> / [] { cleanup...; } = X // catch(...)
);
```

-----

##Testing utilities

-----

####Show current states

```cpp
sm.visit_current_states([](auto state) {
  std::cout << state.c_str() << std::endl;
});
```

####Verify current state

```cpp
assert(sm.is("idle"_s));
```

####Verify current states (Orthogonal Regions)

```cpp
assert(sm.is("region1"_s, "region2"_s, ...));
```

----

##Additional readings

---

http://boost-ext.github.io/msm-lite/user_guide

http://boost-ext.github.io/msm-lite/tutorial

==============================================================================

##Implementation

----

###Transition

> Glue between Front-end and Back-end

----

####Transition
```cpp
template <class TSrcState
        , class TDstState
        , class TEvent = anonymous
        , class TGuard = always
        , class TAction = none>
struct transition {
  template <class SM>
  auto execute(SM &, TEvent &&);

  TGuard guard;
  TAction action;
};
```

----

##Front-end

----

###DSL (Domain Specific language)

```cpp
src_state + event [ guard ] / action -> dst_state
```

----

###State

----

####State
```
template <class TState>
struct state {
  template <class T>
  auto operator=(const T &t) const { return transition<T, state>{ }; }

  template <class T>
  auto operator<=(const T &t) const { return transition<TState, T>{ }; }

  template <class T>
  auto operator+(const T &t) const { return transition<TState, T>{ }; }

  template <class T> requires callable<bool, T>()
  auto operator[](const T &t) const { return transition<TState, T>{ }; }

  template <class T> requires callable<void, T>()
  auto operator/(const T &t) const { return transition<TState, T>{ }; }
};
```

----

###Event

----

####Event
```cpp
template <class>
struct event {
  template <class T> requires callable<bool, T>()
  auto operator[](const T &t) const { return transition<event, T>{ }; }

  template <class T> requires callable<void, T>()
  auto operator/(const T &t) const { return transition<event, T>{ }; }
};
```

----

###Guard

----

###Operators

> `and_, or_, not_`

----

####Base
```cpp
struct operator_base { };
```

####and
```cpp
template <class... Ts>
struct and_ : operator_base {
  template <class TEvent, class TDeps>
  auto operator()(const TEvent &event, TDeps &deps) {
    return (call(std::get<Ns-1>(args), event, deps) && ...);
  }

  tuple<Ts...> args;
};
```

----

###Where

----

####Call / is operator base
```cpp
template<class T, class TEvent, class TDeps>
  requires std::is_base_of_v<operator_base, T>
auto call(T op, const TEvent&, TDeps& deps) {
  return op(event, deps);
}
```

----

####Call / Functor type
```cpp
template<class T, class TEvent, class TDeps>
  requires !std::is_base_of_v<operator_base, T>
auto call(T op, const TEvent& event, TDeps& deps) {
  return call_impl<decltype(&T::operator())>::execute(op, event, deps);
}
```

```cpp
template <class R, class... TArgs>
struct call_impl<R(TArgs...)> {
  template<class T, class TEvent, class TDeps>
  static auto execute(T op, const TEvent& event, TDeps& deps) {
    return op(std::get<TArgs>(tuple_cat(event, deps))...);
  }
};
```

----

###Similary for `or_` and `not_`

----

###User-defined operators

> `namespace msm`

----

####Not
```cpp
template <class T> requires callable<bool, T>()
auto operator!(T&& t) {
  return not_<T>(std::forward<T>(t));
}
```

----

####And
```cpp
template <class T1, class T2>
  requires callable<bool, T1>() && callable<bool, T2>()
auto operator&&(T1&& t1, T2&& t2)  {
  return and_<T1, T2>(std::forward<T1>(t1), std::forward<T2>(t2));
}
```

----

####Or
```cpp
template <class T1, class T2>
  requires callable<bool, T1>() && callable<bool, T2>()
auto operator||(T1&& t1, T2&& t2) {
  return or_<T1, T2>(std::forward<T1>(t1), std::forward<T2>(t2));
}
```

----

###Example

----

####Guards
```cpp
auto true_ = [] { return true; };
auto false_ = [] { return false_; };

auto guards = (!true_ || (true_ && false_ || ![]{ return false; }));
```

####Type
```cpp
static_assert(std::is_same<decltype(guards)
            , not_<or_<and_<false_, not_<[]{return false;}>>>>>{});
```

----

###Action

----

###User-defined operators

> `namespace msm`

----

####Sequence

```cpp
template <class T1, class T2>
  requires callable<void, T1>() && callable<void, T2>()
auto operator,(T1&& t1, T2&& t2) {
  return seq_<T1, T2>(std::forward<T1>(t1), std::forward<T2>(t2));
}
```

----

###Example

----

####Actions
```cpp
auto action = [] { };

auto actions = (action, action, []{}, action);
```

####Type
```cpp
static_assert(std::is_same<decltype(actions), 
              seq_<action, action, []{}, action>>{});
```

----

###Brining it all together

----

####Make transition table
```cpp
template <class... Ts> requires transitional<Ts>()...
auto make_transition_table(Ts&&... ts) {
  return tuple<Ts...>{std::forward<Ts>(ts)...};
}
```

----

###Where

----

####Transitional concept
```cpp
template <class T>
concept bool transitional() {
  return requires(T transition) {
    typename T::src_state;
    typename T::dst_state;
    typename T::event;
    typename T::deps;
    T::initial;
    T::history;
    { transition.execute(...) } -> bool;
  }
}
```

----

###Example

----

####Front-end
```cpp
auto play_song = [] { ... };
auto is_playing =  [] { return true; }

make_transition_table(
  state<class Idle> + play [is_playing] = state<class Wait>
, state<class Idle> + play [!is_playing] / play_song = state<class Play>
, state<class Play> + stop / (stop_song, reset_song) = state<class Idle>
);
```

####Type
```cpp
tuple<
  transition<Idle, Wait, Play, is_playing>
, transition<Idle, Wait, Play, not_<is_playing>, play_song>
, transition<Play, Idle, Stop, always, seq_<stop_song
                                          , reset_song>, play_song>
>
```

----

###DSL limitations

----

####DSL
```cpp
"idle"_s + play [ [] { return true; } ] / action
                ^ ^
                \ /
                 |
/----------------/
\
 Compilation error: `C++11 generalized attributes syntax: [[`
```

####Solution - Parens

```cpp
"idle"_s + play [ ([] { return true; }) ] / action
                  ^                   ^
                  \                   /
                   -------------------
```

----

###Back-end

----

###Operates on transitions

----

###Goals

----

* ###Max run-time performance

* ###Quick compilation times

----

###How?

----

###State Machine

----

####Front-End
```cpp
tuple<
  transition<Idle, Wait, Play, is_playing>
, transition<Idle, Wait, Play, not_<is_playing>, play_song>
, transition<Play, Idle, Stop, always, seq_<stop_song
                                          , reset_song>, play_song>
>
```

####Conversion to Back-End (State Machine)
```cpp
template<class>
struct sm;

template<class... Transitions>
struct sm<tuple<Transitions...>> : core::sm<Transitions...>
{ };
```

----

###Where

----

####State machine
```cpp
template <class... Ts> requires transitional<Ts>()...
class sm { // namespace core
  using states = unique_t<get_state<Ts...>>; // unique list of states
  using events = unique_t<get_event<Ts...>>; // unique list of events
  using deps = unique_t<get_deps<Ts...>>; // unique list of dependencies
  using mappings = mappings_t<Ts...>; // preprocessed event mapping

public:
  template <class... TDeps> requires std::is_base_of_v<TDeps, deps>...
  explicit sm(TDeps &&... deps); // init deps

  template <class TEvent> void process_event(TEvent&&);

private:
  int current_state_ = 0;
  tuple<deps> deps_;
};
```

----

###Details

----

###Unique_t

----

####Utilities
```cpp
template <class...> struct type { };
template <class...> struct type_list { using type = type_list; };
template <class... Ts> struct inherit : Ts... { using type = inherit; };
```

----

####Unique_t
```cpp
template <class...> struct unique;

template <class... Rs, class T, class... Ts>
struct unique<type<Rs...>, T, Ts...> : std::conditional_t<
  std::is_base_of<type<T>, inherit<type<Rs>...>>{},
  unique<type<Rs...>, Ts...>,
  unique<type<Rs..., T>, Ts...>
> { };

template <class... Rs> struct unique<type<Rs...>>
  : type_list<Rs...>
{ };

template <class... Ts> using unique_t =
  typename unique<type<>, Ts...>::type;
```

----

###Boost.Hana vs Boost.MPL vs unique_t

> Boost-1.61

----

####Benchmark
```cpp
using u = decltype(
  hana::unique(hana::sort(hana::make_tuple(event1, event2, event1)))
);
static_assert(make_tuple(event1, event2) == u);
```

```cpp
using u = typename mpl::unique<
  typename mpl::sort<
    mpl::vector<event1, event2, event1>
  , boost::is_same<mpl::_1, mpl::_2>
  >::type;
>;
static_assert(std::is_same<u, mpl::vector<event1, event2>>{});
```

```cpp
using u = unique_t<event1, event2, event1>;
static_assert(std::is_same<u, type_list<event1, event2>>{});
```

----

| Number of elements | unique_t  | Boost.Hana | Boost.MPL |
| ------------------ | --------- | ---------- | --------- |
| 16                 | 0.067s    | 0.620s     | 1.194s    |
| 64                 | 0.078s    | 1.781s     | 2.482s    |
| 128                | 0.085s    | 7.821s     | 10.409s   |

----

###Example

----

####State Machine
```cpp
auto is_playing = [](const player& p, auto event) {
  return p.is_playing(event.song);
};
auto play_song = [](recorder& r) { r.play(); };

sm<
  transition<Idle, Wait, Play, is_playing>
, transition<Idle, Wait, Play, not_<is_playing>, play_song>
, transition<Play, Idle, Stop, always, seq_<stop_song
                                          , reset_song>, play_song>
>
```

####Internal types
```cpp
states = type_list<Idle, Wait, Play>;
events = type_list<Play, Stop>;
deps = tuple_list<const player&, recorder&>;
```

----

###Mappings_t

----

###Approach

----

###Pre-processed transitions

> ####Avoid template 'magic' per event!

----

###Goal

----

####Mappings
```cpp
mappings = {
  Play = {
    Idle = {
      transition<Idle, Wait, Play, is_playing>
    , transition<Idle, Wait, Play, not_<is_playing>, play_song>
    }
  },
  Stop = {
    Play = {
      transition<Play, Idle, Stop, always, seq_<stop_song
                                              , reset_song>, play_song>
    };
  }
};
```

----

###How?

----

###Algorithm

----

[Mappings]
* For each unique event
  * Find transitions with that event
  * For each found transition create a pair of an event and [StateTransitions]

---

[StateTransitions]
* For each unique state
  * Create a pair of a state and transitions from that state and given event

----

###Details

----

###Map

----

####Map
```cpp
template <class, class> struct pair { };

template <class... Ts> struct map : Ts... { };

template <class T> struct no_decay { using type = T; };
template <class TDefault, class> static no_decay<TDefault> lookup(...);

template <class, class TKey, class TValue>
static no_decay<TValue> lookup(pair<TKey, TValue> *);

template <class TDefault, class TKey, class T>
using at_key = decltype(lookup<TDefault, TKey>((T *)0));

template <class T, class TKey, class TDefault = void>
using at_key_t = typename at_key<TDefault, TKey, T>::type;
```

> Used in some modern C++ meta-programming libraries

----

###Boost.Hana vs Boost.MPL vs map

> Boost-1.61

----

####Benchmark
```cpp
constexpr auto m =
  hana::make_map(hana::make_pair(event, transitions), ...);
static_assert(m[event] == transitions);
```

```cpp
using m =
  mpl::map<mpl::pair<event, transitions>...>;
static_assert(boost::is_same<mpl::at<m, event>::type, transitions>{});
```

```cpp
using m =
  map<pair<event, transitions...>>;
static_assert(boost::is_same<at_key_t<m, event>, transitions>{});
```

----

| Number of elements | map     | Boost.Hana | Boost.MPL |
| ------------------ | ------- | ---------- | --------- |
| 16                 | 0.050s  | 0.435s     | 1.110s    |
| 64                 | 0.069s  | 0.923s     | 1.121s    |
| 128                | 0.076s  | 1.186s     | 1.453s    |

----

###Example

----

####State Machine
```cpp
sm<
  transition<Idle, Wait, Play, is_playing>
, transition<Idle, Wait, Play, not_<is_playing>, play_song>
, transition<Play, Idle, Stop, always, seq_<stop_song
                                          , reset_song>, play_song>
>
```

####Mappings
```cpp
mappings = map<
  pair<Play, map<pair<Idle, type_list<
    transition<Idle, Wait, Play, is_playing>,
    transition<Idle, Wait, Play, not_<is_playing>, play_song>
  >>>>,
  pair<Stop, map<pair<Play, type_list<
    transition<Play, Idle, Stop, always,
               seq_<stop_song, reset_song>, play_song>
>>>>>;
```

----

###Usage

----

####Transitions for event 'Play' and state 'Idle'
```cpp
struct empty { };

static_assert(
  std::is_same<
    type_list<
      transition<Idle, Wait, Play, is_playing>,
      transition<Idle, Wait, Play, not_<is_playing>, play_song>
    >,
    at_key_t<at_key_t<mappings, Play, empty>, Idle, empty>
  >{}
);
```

----

###Benchmark

----

| Map size  | Find transitions for event/state |
| --------- | -------------------------------- |
| 16        | 0.002s                           |
| 64        | 0.004s                           |
| 128       | 0.005s                           |

----

###Process event

----

###Generated dispatch/jump table

----

####Jump table

```cpp
template<int N> int f() { return N; }

int main(int argc, char**) {
  int (*jump_table[])() = { f<0>, f<1> }; // f<2>, ... f<N>
  return jump_table[argc - 1]();
}
```

| Command | Exit code |
| ------- | --------- |
| `./jump_table` | 0 |
| `./jump_table 1` | 1 |
| `./jump_table 1 2` | Segmentation fault |

----

####Jump Table - ASM x86-64

```cpp
main:
  movslq  %edi, %rax
  jmpq    *.L_ZZ4mainE10jump_table-8(,%rax,8)

int f<0>():
  xorl    %eax, %eax
  retq

int f<1>():
  movl    $1, %eax
  retq

.L_ZZ4mainE10jump_table:
  .quad   int f<0>()
  .quad   int f<1>()
```

----

###Idea

----

####Generate table for each state
```cpp
void (*dispatch_table[])(TEvent&&) = {
  HandleTEventInState1
, HandleTEventInState2
, ...
, HandleTEventInStateN
};
```

####Jump using current state
```cpp
dispatch_table[current_state_](event);
```

----

###Details

----

####Process event
```cpp
template<class TEvent>
void process_event(TEvent&& event) {
  process_event_impl<at_key_t<mappings, TEvent, do_transition<>>>(
    std::forward<TEvent>(event), states{}
  );
}
```

```cpp
template<class TStateMappings, class TEvent, class... TStates>
void process_event_impl(type_list<TStates...>) {
  void (*dispatch_table[])(TEvent&&) = {
    &at_key_t<TStateMappings, TStates, do_transition<>>::template
      execute<TEvent>...
  };
  dispatch_table[current_state_](std::forward<TEvent>(event));
}
```

----

###Where

----

####Do transition
```cpp
template<class... Ts>
struct do_transition {
  template<class TEvent>
  static auto execute(TEvent&& event) {
    return (Ts{}.execute(std::forward<TEvent>(event)) && ...);
  }
};
```

```cpp
template<>
struct do_transition<> {
  template<class TEvent>
  static auto execute(TEvent&&) {
    assert(false && "no transition!");
    return { };
  }
};
```

----

###Update current state

----

###State type to ID (int)

----

####Type to ID
```cpp
template <std::size_t, class>
struct type_id_type { };

template <class, class...>
struct type_id_impl;

template <std::size_t... Ns, class... Ts>
struct type_id_impl<std::index_sequence<Ns...>, Ts...>
  : type_id_type<Ns, Ts>...
{ };

template <class... Ts>
struct type_id
  : type_id_impl<std::make_index_sequence<sizeof...(Ts)>, Ts...>
{ };
```

----

####Get ID
```cpp
template <class T, int, int N>
constexpr auto get_id_impl(type_id_type<N, T> *) {
  return N;
}
template <class T, int D>
constexpr auto get_id_impl(...) {
  return D;
}
template <class TIds, int D, class T>
constexpr auto get_id()  {
  return get_id_impl<T, D>((TIds *)0);
}
```

####Test
```cpp
using type_ids = type_id<int, double>;
static_assert(-1 == get_id<type_ids, -1, float>());
static_assert(0 == get_id<type_ids, -1, int>());
static_assert(1 == get_id<type_ids, -1, double>());
```

----

###Where/When to update?

----

###Transition::execute

----

####Transitions.Execute
```cpp
template <class TSrcState, class TDstState
        , class TEvent, class TGuard, class TAction>
struct transition {
  template <class TDeps>
  constexpr auto execute(SM & self, const TEvent & event) {
    if (call(guard, event, self.deps_)) { // guards
      self.current_state_ = // set dst state id as the current one
        get_id<type_id<typename SM::states...>, -1, TDstState>();

      call(action, event, self.deps_); // actions
      return true;
    }
    return false;
  }

  TGuard guard; TAction action;
};
```

----

###All in all

----

####Process event (Pseudo-code)
```cpp
+ process_event(e)
|
\->  process_event_impl<mappings<event>>(event)
  |
  \-> dispatch_table = {
    |   mappings<event, states>::transition.execute(event)... }
    |
    \-> dispatch_table[current_state](event);
      |
      \-> transition.execute(event)
```

==============================================================================

##Examples

----

##Generate UML state machine diagram

----

####Dump transitions
```cpp
template <class SM>
void dump(const SM&) noexcept {
  std::cout << "@startuml" << std::endl << std::endl;
  dump_transitions(typename SM::transitions{});
  std::cout << std::endl << "@enduml" << std::endl;
}

template <template <class...> class T, class... Ts>
void dump_transitions(const T<Ts...>&) noexcept {
  (dump_transition<Ts>(), ...);
}
```

----

####Dump transition
```cpp
template <class T>
void dump_transition() noexcept {
  const auto src_state = msm::state<typename T::src_state>::c_str();
  const auto dst_state = msm::state<typename T::dst_state>::c_str();

  if (T::initial) {
    std::cout << "[*] -> " << src_state << std::endl;
  }

  std::cout << src_state << " -> " << dst_state << " : "
            << typeid(typename T::event) << "["
            << typeid(typename T::guard) << "] / "
            << typeid(typename T::action);
}
```
----

####Example - transition table
```cpp
struct plant_uml {
  auto configure() const noexcept {
    using namespace msm;
    return make_transition_table(
       *"idle"_s + event<e1> = "s1"_s
      , "s1"_s + event<e2> [ guard ] / action = "s2"_s
      , "s2"_s + event<e3> [ guard ] = "s1"_s
      , "s2"_s + event<e4> / action = X
    );
  }
};
```
-----

###Output

```cpp
@startuml
  [*] -> idle
  idle -> s1 : e1
  s1 -> s2 : e2 [guard] / action
  s2 -> s1 : e3 [guard]
  s2 -> terminate : e4 / action
@enduml
```

![UML](images/uml.png)

----

##More Examples

---

[Hello World](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#hello-world)

[Events](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#events) |
[States](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#states) |
[Actions Guards](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#actions-guards) |
[Transitions](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#transitions)

[Orthogonal Regions](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#orthogonal-regions) |
[Composite](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#composite) |
[History](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#history)

[Error handling](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#error-handling) |
[Logging](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#logging) |
[Testing](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#testing)

[Runtime Dispatcher](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#runtime-dispatcher) |
[eUML Emulation](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#euml-emulation) |
[Dependency Injection](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#dependency-injection)

[SDL2 Integration](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#sdl2-integration) |
[Plant UML Integration](https://raw.githubusercontent.com/boost-ext/msm-lite/master/example#plant-uml-integration)

==============================================================================

##Questions?

* Documentation
    * http://boost-ext.github.io/msm-lite

* Source Code
    * https://github.com/boost-ext/msm-lite

* Try it online
    * http://boost-ext.github.io/msm-lite/examples

==============================================================================

##Thank you

					</script>

				</section>

			</div>
		</div>

		<script src="lib/js/head.min.js"></script>
		<script src="js/reveal.js"></script>

		<script>

			// Full list of configuration options available at:
			// https://github.com/hakimel/reveal.js#configuration
			Reveal.initialize({

        // Display controls in the bottom right corner
        controls: true,

        // Display a presentation progress bar
        progress: true,

        // Display the page number of the current slide
        slideNumber: true,

        // Push each slide change to the browser history
        history: true,

        // Enable keyboard shortcuts for navigation
        keyboard: true,

        // Enable the slide overview mode
        overview: true,

        // Vertical centering of slides
        center: true,

        // Enables touch navigation on devices with touch input
        touch: true,

        // Loop the presentation
        loop: false,

        // Change the presentation direction to be RTL
        rtl: false,

        // Turns fragments on and off globally
        fragments: false,

        // Flags if the presentation is running in an embedded mode,
        // i.e. contained within a limited portion of the screen
        embedded: false,

        // Flags if we should show a help overlay when the questionmark
        // key is pressed
        help: true,

        // Flags if speaker notes should be visible to all viewers
        showNotes: false,

        // Number of milliseconds between automatically proceeding to the
        // next slide, disabled when set to 0, this value can be overwritten
        // by using a data-autoslide attribute on your slides
        autoSlide: 0,

        // Stop auto-sliding after user input
        autoSlideStoppable: true,

        // Enable slide navigation via mouse wheel
        mouseWheel: true,

        // Hides the address bar on mobile devices
        hideAddressBar: true,

        // Opens links in an iframe preview overlay
        previewLinks: false,

        // Transition style
        transition: 'convex', // none/fade/slide/convex/concave/zoom

        // Transition speed
        transitionSpeed: 'default', // default/fast/slow

        // Transition style for full page slide backgrounds
        backgroundTransition: 'default', // none/fade/slide/convex/concave/zoom

        // Number of slides away from the current that are visible
        viewDistance: 3,

        // Parallax background image
        parallaxBackgroundImage: '', // e.g. "'https://s3.amazonaws.com/hakim-static/reveal-js/reveal-parallax-1.jpg'"

        // Parallax background size
        parallaxBackgroundSize: '', // CSS syntax, e.g. "2100px 900px"

        // Number of pixels to move the parallax background per slide
        // - Calculated automatically unless specified
        // - Set to 0 to disable movement along an axis
        parallaxBackgroundHorizontal: null,
        parallaxBackgroundVertical: null,

				// Optional reveal.js plugins
				dependencies: [
					{ src: 'lib/js/classList.js', condition: function() { return !document.body.classList; } },
					{ src: 'plugin/markdown/marked.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
					{ src: 'plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
					{ src: 'plugin/highlight/highlight.js', async: true, callback: function() { hljs.initHighlightingOnLoad(); } },
					{ src: 'plugin/zoom-js/zoom.js', async: true },
					{ src: 'plugin/notes/notes.js', async: true }
				]
			});

		</script>

	</body>
</html>
